package william.list;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author ZhangShenao
 * @date 2024/3/18
 * @description <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">...</a>
 */
public class Leetcode23_合并K个升序链表 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 借助堆实现
     * 创建一个长度为N的小根堆,保存所有链表的头节点,N=链表数量
     * 将全部根节点放入堆中
     * 每次从堆中取出堆顶元素,它就是当前最小的节点,将它追加到新链表末尾,并将该节点的后继节点放入堆中
     * <p>
     * 时间复杂度O(N*logN) 遍历链表O(N)x堆中操作O(logN)
     * 空间复杂度O(N) 需要额外申请一个堆,堆的长度=链表数量
     */
    public ListNode mergeKLists(ListNode[] lists) {
        //边界条件校验
        if (lists == null || lists.length < 1) {
            return null;
        }

        //创建一个长度为N的小根堆,保存所有链表的头节点,N=链表数量
        PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, Comparator.comparingInt(o -> o.val));
        //首先将所有根节点放入堆中
        for (ListNode n : lists) {
            if (n != null) {
                heap.offer(n);
            }
        }

        //借助哑头节点
        ListNode dummy = new ListNode();
        ListNode merged = dummy;

        //每次从堆中取出堆顶元素,它就是当前最小的节点,将它追加到新链表末尾,并将该节点的后继节点放入堆中
        while (!heap.isEmpty()) {
            //追加当前最小节点
            ListNode min = heap.poll();
            merged.next = min;
            merged = merged.next;

            //后继节点入堆
            if (min.next != null) {
                heap.offer(min.next);
            }
        }

        //返回头节点
        return dummy.next;

    }
}
